package suanfa.datastructure.Graph;

import suanfa.datastructure.Array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Testgraph {
    private ArrayList<String> vertexList;
    private int[][] edges;
    private int num;
    private boolean[] isvisited;
    public Testgraph(int n){
        edges=new int[n][n];
        num=0;
        vertexList=new ArrayList<>(n);
    }

    public void insertvetex(String vertex){
        vertexList.add(vertex);
    }

    public void insertEdge(int v1,int v2,int g){
        edges[v1][v2]=g;
        edges[v2][v1]=g;
        num++;
    }

    public String getindex(int d){
        return vertexList.get(d);
    }

    public int getnum(){
        return num;
    }

    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }
    public void show(){
        for(int[] a:edges){
            System.out.println(Arrays.toString(a));
        }
    }


    //深度优先遍历dfs
    public int getfirst(int index){//得到第一个邻接点的下标
        for(int i=0;i<vertexList.size();i++){
            if(edges[index][i]>0){
                return i;
            }
        }
        return -1;
    }

    public int getnext(int v1,int v2){//根据前一个邻接结点得到下一个邻接结点
        for(int i=v2+1;i<vertexList.size();i++){
            if(edges[v1][i]>0){
                return i;
            }
        }
        return -1;
    }

    private void dfs(boolean[] isvisited,int i){
        System.out.println(vertexList.get(i)+" ");
        isvisited[i]=true;
        int w=getfirst(i);
        while(w!=-1){
            if(!isvisited[w]){
                dfs(isvisited,w);
            }
            w=getnext(i,w);
        }
    }


    public void dfs(){//重载，遍历所有结点，并进行dfs
        isvisited=new boolean[vertexList.size()];
        for(int i=0;i<vertexList.size();i++){
            if(!isvisited[i]){
                dfs(isvisited,i);
            }
        }
    }


        private void bfs(boolean[] isvisited,int i){//bfs广度优先遍历
            int u;
            int w;
            LinkedList queue=new LinkedList();
            System.out.println(getindex(i)+"=>");
            isvisited[i]=true;
            queue.addLast(i);

            while(!queue.isEmpty()){
                u=(Integer)queue.removeFirst();
                w=getfirst(u);
                while(w!=-1)
                {
                   if(!isvisited[w]){
                       System.out.println(getindex(w)+"=>");
                       isvisited[w]=true;
                       queue.addLast(w);
                   }
                    w=getnext(u,w);
                }

            }

        }



    public static void main(String[] args) {
        Testgraph graph=new Testgraph(5);
        String[] a={"A","B","C","D","E"};

    }
}
